/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package clustering;

import java.util.Enumeration;
import java.util.Hashtable;
import java.util.LinkedList;
import lucene.Analyzers.AnalyzerUtils;
import org.apache.lucene.index.TermFreqVector;

/**
 *
 * @author Livia
 */
public class DBSCAN extends ClusteringAlgorithm{
    public final static int MIN_PORCENTAGEM_DENSIDADE = 5; //(20% dos tweets)
    public final static double REGION_DISTANCIA_ALTERNATIVA = 0.5;     
    public final static double REGION_DISTANCIA_COSSENO = 0.9;     
    public final static double REGION_DISTANCIA_TANIMOTO = 0.95; 
    private final static int UNDEFINED = -1;
    private final static int RUIDO = -2;
    
    private int minNumMembros;
    private LinkedList<String> searchTerms;
    private int numVectors;
    private TermFreqVector[] termVectors;
    private int[] clusterAtualDosVetores;
    private double[] distanciaAtualDosVetores;
    private boolean[] vetoresVisitados;
    public int clusterAtual;
    //private boolean[] vetoresRuido;
    private int tipoDistancia;
    private LinkedList <Hashtable> clusters;
    private Hashtable<String, Integer> popTermsClusterTop1;
    private Hashtable<String, Integer> popTermsClusterTop2;
    private double maxDistRegion;
    private Hashtable<Integer, Integer> clusterTop1, clusterTop2;
    
    public DBSCAN (TermFreqVector[] vectors, LinkedList<String> searchTerms){
        this.termVectors = vectors;
        this.numVectors = termVectors.length;
        this.minNumMembros = numVectors / DBSCAN.MIN_PORCENTAGEM_DENSIDADE; 
        this.searchTerms = searchTerms;    
        this.clusters = new LinkedList <Hashtable>();    
        this.distanciaAtualDosVetores = new double[numVectors];
                        
        clusterAtualDosVetores = new int[numVectors];
        vetoresVisitados = new boolean[numVectors];        
        initVectors();
    }

    public void initVectors() {
        int i;
        for (i = 0; i < numVectors; i++){
            vetoresVisitados[i] = false;
        }
        for (i = 0; i < numVectors; i++){
            clusterAtualDosVetores[i] = UNDEFINED;
        }
    }
    
    public void run(int tipoDistancia, int topQuantos){
        this.tipoDistancia = tipoDistancia;       
                
        if(tipoDistancia == DBSCAN.DISTANCIA_ALTERNATIVA)
            this.maxDistRegion = DBSCAN.REGION_DISTANCIA_ALTERNATIVA;        
        else if(tipoDistancia == DBSCAN.DISTANCIA_COSSENO)
            this.maxDistRegion = DBSCAN.REGION_DISTANCIA_COSSENO;    
        else if(tipoDistancia == DBSCAN.DISTANCIA_TANIMOTO)
            this.maxDistRegion = DBSCAN.REGION_DISTANCIA_TANIMOTO;  
        
         
        LinkedList<Integer> regionN = new LinkedList<Integer>();
        Hashtable<Integer, Integer> novoCluster;        
        novoCluster = new Hashtable <Integer, Integer>();
        this.clusters.add(novoCluster); 
        this.clusterAtual = 0; 
                
        for (int i = 0; i<numVectors; i++){
            if (this.vetoresVisitados[i] == false){
                this.vetoresVisitados[i] = true;
                regionN = regionQuery (i, this.maxDistRegion);
                if (regionN.size() < this.minNumMembros)
                    this.clusterAtualDosVetores[i] = RUIDO;
                else{                                       
                    expandCluster (i, regionN, clusterAtual, this.maxDistRegion, this.minNumMembros);                    
                    novoCluster = new Hashtable <Integer, Integer>();
                    this.clusters.add(novoCluster); 
                    this.clusterAtual = clusterAtual + 1;
                }
            }
        }        
        printClusters();
        computePopularWords(topQuantos);  
        System.gc();
            
    }                      

    //retorna todos os vetores da regiao, inclusive o central dado como parametro
   private LinkedList<Integer> regionQuery(int vetor, double MAX_DISTANCIA) {
        
        LinkedList<Integer> region = new LinkedList<Integer>();        
        double distance;
        TermFreqVector tv1, tv2;
        tv1 = this.termVectors[vetor];
        
        for (int i = 0; i < this.numVectors; i++){
            tv2 = this.termVectors[i];            
            
            if(tipoDistancia == DBSCANv2.DISTANCIA_ALTERNATIVA){
                distance = this.calculateDistance_alternativa(tv1, tv2);
            }
            else if(tipoDistancia == DBSCANv2.DISTANCIA_COSSENO){
                distance = this.calculateDistance_cosseno(tv1, tv2);           
            }  
            else if(tipoDistancia == DBSCANv2.DISTANCIA_TANIMOTO){
                distance = this.calculateDistance_tanimoto(tv1, tv2);
            }
            else
                return null;
            
            if (distance <= MAX_DISTANCIA){
                region.add(i);               
            }
            
            this.postMessage("Distance from " + vetor + " to " + i + " = " + distance);
        }        
        return region;      
   }

    private void expandCluster(int vetor, LinkedList<Integer> regionN, 
            int numCluster, double MIN_DISTANCIA, int minNumMembros) {
        
        LinkedList<Integer> regionNlinha;
        this.clusterAtualDosVetores[vetor] =  numCluster;
        this.clusters.get(numCluster).put(vetor, vetor);
        
        int v = 0;
        while (!regionN.isEmpty()){
            v = regionN.getFirst();
            if(this.vetoresVisitados[v] == false){
                this.vetoresVisitados[v] = true;
                regionNlinha = regionQuery(v, MIN_DISTANCIA);
                if(regionNlinha.size() >= this.minNumMembros){
                    regionN = joinRegions (regionN, regionNlinha);
                }
            }
            if (this.clusterAtualDosVetores[v] == UNDEFINED || 
                    this.clusterAtualDosVetores[v] == RUIDO){
                this.clusterAtualDosVetores[v] = numCluster;   
                this.clusters.get(numCluster).put(v, v);
            }
            regionN.removeFirst();
        }
    }

    private LinkedList <Integer> joinRegions(LinkedList <Integer> regionN, 
            LinkedList <Integer> regionNlinha) {
        //coloca regionNlinha em regionN

        for (int i = 0; i< regionNlinha.size(); i++){
            int v = regionNlinha.get(i);
            regionN.addLast(v);
        }
        return regionN;
    }
    
    private double calculateDistance_cosseno(TermFreqVector tv1, TermFreqVector tv2){
        double nominator = 0, denominatorA = 0, denominatorB = 0, denominator = 0;
        double x1, x2;
        int numIntv2;
        String key;
        
        //checa todos os termos de tv1
        for (int i = 0; i< tv1.size(); i++){
            key = tv1.getTerms()[i]; 
            if (!this.isASearchTerm(key)){
                x1 = tv1.getTermFrequencies()[i];     
                numIntv2 = tv2.indexOf(key);
                if (numIntv2 != -1){ //se tem nos dois.....
                    x2 = tv2.getTermFrequencies()[numIntv2];
                    nominator = nominator + x1*x2; // somatoria Ai ^ Bi
                }
                denominatorA = denominatorA + Math.pow(x1, 2);   // somatoria Ai ^2   
            }
        }
        
        //depois checa todos os termos de center
        for (int i = 0; i< tv2.size(); i++){  
            if (!this.isASearchTerm(tv2.getTerms()[i])){
                x2 = tv2.getTermFrequencies()[i];            
                denominatorB = denominatorB + Math.pow(x2, 2);   //somatoria Bi ^2   
            }
        }
        
        denominator = Math.sqrt(denominatorA) * Math.sqrt(denominatorB);
        return 1 - nominator / denominator;  
        //se cos = 0 entao 90 graus, mais distante possivel (distancia 1)
        // se cos = 1 entao é o mesmo vetor, mas proximo possivel (distancia 0)
                                            
    }
    
    private double calculateDistance_tanimoto(TermFreqVector tv1, TermFreqVector tv2){
        double x1DOTx2 = 0, modtv1 = 0, modtv2 = 0;
        int x2;
        int x1;
        int numIntv2;
        String key;
        
        //checa todos os termos de tv1
        for (int i = 0; i< tv1.size(); i++){
            key = tv1.getTerms()[i]; 
            if (!this.isASearchTerm(key)){
                x1 = tv1.getTermFrequencies()[i];
                numIntv2 = tv2.indexOf(key);            
                if (numIntv2 != -1){ //se tem nos dois.....
                    x2 = tv2.getTermFrequencies()[numIntv2];
                    x1DOTx2 = x1DOTx2 + x2 * x1;
                }   
                modtv1 = modtv1 + Math.pow(x1, 2);   
            }
        }        
        
         for (int i = 0; i< tv2.size(); i++){ //## Checa se eh assim que usa enumeration
            if (!this.isASearchTerm(tv2.getTerms()[i])){
                x2 = tv2.getTermFrequencies()[i];            
                modtv2 = modtv2 + Math.pow(x2, 2);    
            }
        }        
        return (1 - (x1DOTx2 / (modtv1 + modtv2 - x1DOTx2)));                                              
    }
    
    private double calculateDistance_alternativa(TermFreqVector tv1, TermFreqVector tv2){
        double denominador = 1;
        int numIntv2;
        String key;
        
        //checa todos os termos de tv1
        for (int i = 0; i< tv1.size(); i++){
            key = tv1.getTerms()[i];     
            if (!this.isASearchTerm(key)) {
                numIntv2 = tv2.indexOf(key);                 
                if (numIntv2 != -1){ //se tem nos dois.....                    
                    denominador = denominador * 2;       
                    if (this.isHashtag(key));
                        denominador = denominador * 2;    
                }  
            }
        }
        return 1/denominador;
    }
    
    public boolean isASearchTerm(String s){
        for (int i = 0; i< this.searchTerms.size(); i++){
            if (s.equalsIgnoreCase(searchTerms.get(i)))      
                 return true;
        }
        return false;
    }
    
    public boolean isHashtag(String s){
        return s.startsWith("#");
    }

    public void printClusters(){       
        Enumeration<Integer> enumOfMembers; 
        int i, member;
        
        for(int n = 0; n < this.clusters.size(); n++){                
            this.postMessage("**** CLuster " + n + "*****");
            enumOfMembers = this.clusters.get(n).keys();
            i = 1;
            while (enumOfMembers.hasMoreElements()){
                member = enumOfMembers.nextElement();
                this.postMessage(i+ ") " + member);
                AnalyzerUtils.displayTermVector(this.termVectors[member]);                
                i++;
            }
        }
    }

    public void computePopularWords(int topQuantos) {            
        clusterTop1 = this.clusters.get(0);
        clusterTop2 = null;
        //Hashtable<Integer, Integer> clusterTop2 = this.clusters.get(0);
        
        for (int i = 1; i < this.clusters.size(); i++){
            if( this.clusters.get(i).size() > clusterTop1.size()){
                clusterTop2 = clusterTop1;
                clusterTop1 = this.clusters.get(i);
            }
            else if (i == 1)
                clusterTop2 = this.clusters.get(i);  
            else if( this.clusters.get(i).size() > clusterTop2.size()) 
                clusterTop2 = this.clusters.get(i);      
        }
        
        this.postMessage("Size top1 Cluster = " + clusterTop1.size());
        this.postMessage("Size top2 Cluster = " + clusterTop2.size());
        
        this.popTermsClusterTop1 = computePopularWordsOfCluster(clusterTop1,topQuantos);
        this.popTermsClusterTop2 = computePopularWordsOfCluster(clusterTop2,topQuantos);
        
        this.printPopularWords(); 
    }

    public void postMessage(String string) {
        System.out.print("\n-->DBSCAN Algo: "+ string);    
    }
    
    /*public Hashtable<String, Integer> computePopularWordsOfCluster(
            Hashtable<Integer, Integer> cluster, int topQuantos){
        
        Hashtable<String, Integer> termFreqTable = new Hashtable<String, Integer>();
        Enumeration<Integer> docs = cluster.keys();
        int doc, i=0, j=0, freq;
        String term;

         //coloca todos os termos em uma hashtable
        while(docs.hasMoreElements()){
            doc = docs.nextElement();
            for (j=0; j< this.termVectors[i].size(); j++){
                freq = 0;
                term = this.termVectors[i].getTerms()[j];
                if (!isASearchTerm(term) && !isHashtag(term)){
                    if (termFreqTable.containsKey(term)){
                        freq = termFreqTable.get(term);
                    }
                    termFreqTable.put(term, freq + 1);
                }
            }
            i++;
        }     
        
        //procura por termos com freq entre as top N;
        Enumeration<String> keyEnum;       
        Hashtable<String,Integer> popTermsTable = new Hashtable<String,Integer>();
        String key;        
              
        int auxFreq = -1, topFreq;
        for (int t = 0; t < topQuantos; t++){  
            topFreq = getMaxFreqEnum(termFreqTable, auxFreq);
            keyEnum = termFreqTable.keys();
            while (keyEnum.hasMoreElements()){
                key = keyEnum.nextElement();
                if( (Integer)termFreqTable.get(key) == topFreq)
                    popTermsTable.put(key,topFreq);
            }
            auxFreq = topFreq;            
        } 
        
        return popTermsTable;
    }*/
    
    public Hashtable<String, Integer> computePopularWordsOfCluster(
            Hashtable<Integer, Integer> cluster, int topQuantos){
        
        Hashtable<String, Integer> termFreqTable = new Hashtable<String, Integer>();
        Enumeration<Integer> vectorsOfCluster = cluster.keys();
        int vector, j=0, freq;
        String term;

         //coloca todos os termos em uma hashtable
        while(vectorsOfCluster.hasMoreElements()){
            vector = vectorsOfCluster.nextElement();
            for (j=0; j< this.termVectors[vector].size(); j++){
                freq = 0;
                term = this.termVectors[vector].getTerms()[j];
                if (!isASearchTerm(term) && !isHashtag(term)){
                    if (termFreqTable.containsKey(term)){
                        freq = termFreqTable.get(term);
                    }
                    termFreqTable.put(term, freq + 1);
                }
            }
        }     
        
        //procura por termos com freq entre as top N;
        Enumeration<String> termsOfCluster;       
        Hashtable<String,Integer> popTermsTable = new Hashtable<String,Integer>();      
              
        int auxFreq = -1, topFreq;
        for (int t = 0; t < topQuantos; t++){  
            topFreq = getMaxFreqEnum(termFreqTable, auxFreq);
            termsOfCluster = termFreqTable.keys();
            while (termsOfCluster.hasMoreElements()){
                term = termsOfCluster.nextElement();
                if( (Integer)termFreqTable.get(term) == topFreq)
                    popTermsTable.put(term,topFreq);
            }
            auxFreq = topFreq;            
        } 
        
        return popTermsTable;
    }
    
    private int getMaxFreqEnum(Hashtable<String,Integer> termFreqTable, int teto){
        int top = 0, aux;
        Enumeration<Integer> freqEnum = termFreqTable.elements();
        while(freqEnum.hasMoreElements()){
            aux = freqEnum.nextElement();
            if ( aux > top && (aux < teto || teto == -1))
                top = aux;
        }
        return top;
    }

    public void printPopularWords() {
         Enumeration <String> topTerms; int i;
        String term;
                
        topTerms = this.popTermsClusterTop1.keys(); i = 0;
        this.postMessage("\n *** Pop Words Center 1 ***");
        while(topTerms.hasMoreElements()){
            term = topTerms.nextElement();
            this.postMessage(i + ") Term: " + term + " Freq: " + 
                    this.popTermsClusterTop1.get(term));
        }
        
        topTerms = this.popTermsClusterTop2.keys(); i = 0;
        this.postMessage("\n *** Pop Words Center 2 ***");
        while(topTerms.hasMoreElements()){
            term = topTerms.nextElement();
            this.postMessage(i + ") Term: " + term + " Freq: " + 
                    this.popTermsClusterTop2.get(term));
        }
    }
    
    public Enumeration<String> getListPopWordsCluster(int nCluster){
        Enumeration <String> e;
        if (nCluster == 1)
            e = this.popTermsClusterTop1.keys();
        else
            e = this.popTermsClusterTop2.keys();
        return e;
    }

    @Override
    public int[] getSizeTopClusters() {
        int[] size = new int[2];
        size[0] = this.clusterTop1.size();
        size[1] = this.clusterTop2.size();
        return size;
    }
        
     
}
